The present invention relates to methods and apparatus for detecting and correcting errors in transmitted or stored data, and more particularly, to methods and apparatus for detecting and correcting errors using limited working storage.
Error-correction codes (ECC) are commonly used in many of today""s computer and telecommunication systems. For example, error detection and correction codes are used to minimize the number of errors and/or erasures (missing or known to be corrupted data) caused by unreliable communication channels, such as digital wireless transmission systems. In another example, error detection and correction codes are used to minimize the number of errors and/or erasures that are produced by high speed and high density magnetic or optical storage devices.
For many error correction codes (ECC), the data to be transmitted are processed mathematically to generate redundancy symbols, which are appended to the data to form code words, which are then transmitted. When the code words are received, the redundancy symbols are used to decode the received code words back into the original data.
Generally, more protection is provided by using more redundancy symbols. There is, however, an upper bound or xe2x80x9cchannel capacityxe2x80x9d on the performance of any given channel. The xe2x80x9cchannel capacityxe2x80x9d refers to the maximum data transmission rate (or recording density) that can be achievable for a given channel while maintaining an arbitrarily low error rate. Ultimately, the channel capacity is a function of the channel bandwidth and the signal to noise ratio (SNR) of the channel. Error correction codes can be thought of as helping to improve the channel performance by increasing the effective SNR.
There are many approaches for encoding/decoding the user data to maximize the reliability and efficiency of a channel. Ultimately, the goal is to design a system that approaches the channel capacity while minimizing the implementation complexity and cost. Block error-correcting codes are often used because of their good error correction properties and low implementation complexity and cost. The Reed-Solomon (RS) code is a particular type of block error-correction code.
Block codes typically encode a K-symbol input block of source data into an N-symbol output block or code word, where N-K is the number of redundancy symbols.
The code words are transmitted through the communication medium and decoded by a receiver. The encoding process includes a mathematical operation over the input block such that the output code words are different from one another by a parameter referred to as the minimum distance of the code dmin. The minimum distance dmin determines the amount of noise that the system can tolerate before a received code word is decoded erroneously.
With Reed-Solomon (RS) codes, the data stream is processed as a sequence of symbols, where the symbols are typically selected from a finite field GF(2w), where the parameter xe2x80x9cwxe2x80x9d denotes the number of binary data bits per symbol. Each symbol of the K-symbol input block represents the coefficients of a data polynomial D(x). The redundancy symbols (which are also represented as a polynomial W(x)) are then computed as the modulo division of the input data polynomial D(x) divided by a generator polynomial G(x):
W(x)=(xmxc2x7D(x))MOD G(x)xe2x80x83xe2x80x83Equation (1)
where m is the degree of the generator polynomial, which equals the number of redundancy symbols. The redundancy polynomial W(x) is then added to the data polynomial D(x) to generate a code word polynomial C(x):
C(x)=(xmxc2x7D(x))+W(x)xe2x80x83xe2x80x83Equation (2)
Those skilled in the art understand that the encoder circuitry for performing the above operations can be implemented with minimum cost using a linear feedback shift register (LFSR).
After encoding, the code word C(x) is transmitted through the noisy communication channel, wherein the received code word R(x) equals the transmitted code word C(x) plus an error polynomial E(x). The received code word R(x) is often corrected by: (1) computing the values of the error syndromes si; (2) computing the coefficients of an error locator polynomial using the error syndromes si; (3) computing the roots of the error locator polynomial, the logs of the roots being the error locations; and (4) computing the error values using the error syndromes si and the roots of the error locator polynomial.
The error syndromes si are computed as the modulo division of the received code word polynomial R(x) divided by the factors of the generator polynomial G(x):
Si=R(x)MOD(x+xcex1i)xe2x80x83xe2x80x83Equation (3)
when                               G          ⁡                      (            x            )                          =                              ∏                          i              =              0                                      m              -              1                                ⁢                      xe2x80x83                    ⁢                      (                          x              +                              α                i                                      )                                              Equation        ⁢                  xe2x80x83                ⁢                  (          4          )                    
where xcex1 is a primitive element of the finite field GF(2w). In practice, the error syndromes si are often calculated using a relation similar to:                               [                                                                      s                  1                                                                                                      s                  2                                                                                                      s                  3                                                                                    ⋮                                                                                      s                                      n                    -                    k                                                                                ]                =                              [                                                                                r                    1                                                                                                                    r                    2                                                                                                                    r                    3                                                                                                ⋮                                                                                                  r                    n                                                                        ]                    ⁢                      xe2x80x83                    [                                                                      H                                      1                    ,                    1                                                                                                H                                      2                    ,                    1                                                                                                H                                      3                    ,                    1                                                                              ⋯                                                              H                                      n                    ,                    1                                                                                                                        H                                      1                    ,                    2                                                                                                H                                      2                    ,                    2                                                                              ⋯                                            ⋯                                                              H                                      n                    ,                    2                                                                                                      ⋮                                            ⋮                                            ⋰                                            ⋯                                            ⋮                                                                    ⋮                                            ⋮                                            ⋮                                            ⋰                                            ⋮                                                                                      H                                      1                    ,                                          n                      -                      k                                                                                                                    H                                      2                    ,                                          n                      -                      k                                                                                                                    H                                      3                    ,                                          n                      -                      k                                                                                                  ⋯                                                              H                                      n                    ,                                          n                      -                      k                                                                                                    ]                                    Equation        ⁢                  xe2x80x83                ⁢                  (          5          )                    
where vector xe2x80x9csxe2x80x9d is the syndrome vector, vector xe2x80x9crxe2x80x9d is the received code word, and matrix xe2x80x9cHxe2x80x9d is the decoding matrix calculated from the MOD(x+xcex1i) term of Equation (3).
Techniques for performing the remaining steps of the decoding process, including computing the error locator polynomial, computing the roots of the error locator polynomial, and computing the error values, are well known by those skilled in the art. See, for example, U.S. Pat. No. 5,446,743 to Zook, U.S. Pat. No. 5,715,262 to Gupta, U.S. Pat. No. 6,031,875 to Im, U.S. Pat. No. 6,041,431 to Goldstein, and U.S. Pat. No. 6,047,395 to Zook.
The use of erasure pointers is a technique that is commonly used to increase the power of an error correction code (ECC). An erasure pointer is typically an address pointing to a symbol location of a code word where an error is likely to have occurred. For example, an erasure pointer may be generated by a transport layer that detects timing phase errors, marginal amplitude signals, etc. Alternatively, or in addition, the erasure pointers may be generated by another layer of ECC coding. Regardless of how the erasure pointers are generated, the erasure pointers can be used to augment the error correction code by providing information in addition to the error syndromes si.
An erasure polynomial is commonly generated using the erasure pointers, where each root of the erasure polynomial replaces a root of the error locator polynomial. If the number of erasure pointers equals the number of error syndromes, then the erasure polynomial replaces the error locator polynomial.
Since the erasure pointer corresponds to the error location, only an error value needs to be computed for each erasure pointer, thereby accounting for the increase in the correction capability of the code. Without erasure pointers, the code is capable of correcting INT(m/2) code word symbols, where xe2x80x9cmxe2x80x9d is the degree of the generator polynomial (and the number of error syndromes). With erasure pointers, the code is capable of correcting n+INT((mxe2x88x92n)/2) code word symbols, where xe2x80x9cnxe2x80x9d is the number of erasure pointers. Thus, the error correction capability of the code in effect doubles when the number of erasure pointers equals the number of error syndromes, i.e., when xe2x80x9cnxe2x80x9d equals xe2x80x9cmxe2x80x9d.
In most applications, the receiver includes working storage (e.g., Random If Access Memory) for providing short-term storage during the decoding process. For relatively high-speed applications, working storage is preferred over slower secondary storage (e.g., magnetic or optical disks) because the read and write times of most secondary storage devices are inadequate.
While working storage is fast, it is relatively expensive. Accordingly, reducing the amount of working storage would be beneficial. In most implementations, the amount of working storage that is required for decoding linear block codes is related to the size of the blocks. Therefore, one approach for reducing the required working storage is to reducing the block size. However, reducing the block size increases the redundancy overhead, which as described above, is undesirable in many cases.
Due to variations in the channel characteristics, e.g., such as multi-path and fading, received error rates may dramatically increase during short periods or bursts of time, which produce a burst of errors. If an error code is designed to provide adequate protection during these high error rate periods, the error code would impose excess redundancy during those times when the error rates are smaller.
A common technique that is used to accommodate such error bursts is to interleave symbols of different protected blocks during transmission, which spreads the errors of an error burst among several of the protected blocks. This reduces the probability that the error correction limit of any single block will be exceeded. Interleaving can be used to reduce the overall number of redundancy symbols required for a given post-correction error rate.
When the data from different blocks are interleaved, the amount of working storage that is required typically increases. The total working storage required for de-interleaving and decoding linear block codes is typically proportional to the degree of interleave required to accommodate the maximum time duration of an error burst given the transmitted bandwidth, and the block size. Accordingly, systems that accommodate long burst errors can require significant amounts of interleave and thus significant amounts of working storage.
What would be desirable, therefore, is a method and apparatus for performing error-correction while minimizing the amount of working storage. This may allow a maximum number of errors to be corrected with a minimum amount of working storage. Alternatively, larger block sizes or higher transmission rates may be used for a given amount of working storage, which may minimize excess redundancy and increase the xe2x80x9cchannel capacityxe2x80x9d of the communication channel.
The present invention overcomes many of the disadvantages of the prior art by providing methods and apparatus for performing error-correction while minimizing the amount of working storage. When decoding linear block codes, the error syndromes si are first calculated. To minimize the working storage required when calculating the error syndromes, the present invention calculates the error syndromes incrementally as each symbol of the code word is received. That is, as each symbol, riof the code word is received, the received symbol, ri is multiplied by the entries in the xe2x80x9cithxe2x80x9d column of a decoding matrix, resulting in intermediate syndrome components. The intermediate syndrome components are then added to the appropriate entry in a syndrome vector. Once all symbols ri are received, the syndrome vector contains the error syndromes si for the received code word.
A benefit of using this approach is that all of the symbols of the incoming code word need not be stored in the working store simultaneously. Rather, each symbol is sequentially stored in the working store and then removed from the working store after the corresponding intermediate syndrome components are calculated. For later reference, all of the non-redundant symbols are stored in a secondary store, as the secondary store is much cheaper than the working store. While the present invention may not reduce the total amount of storage required for decoding a code word, it does allocate the storage requirements among both the working store and a secondary store. By minimizing the working store, significant cost savings may be achieved.
Once the syndrome vector is calculated, the location of the errored symbols can be identified using the syndrome vector, and an error magnitude for each errored symbol can be calculated, as described above.
To increase the power of the error correction code (ECC), it is contemplated that erasure locations may be identified prior to decoding the received code word. The erasure locations may be identified by, for example, detecting a timing phase error during tranmission, another ECC layer, etc. The erasure locations may then be used to augment the error correction code. Preferably, the erasure locations would be used in conjunction with the syndrome vector to identify the location of errored symbols in the received code word.
In one embodiment, the errored symbols are fetched from the secondary store once the errored symbols have been identified. The previously calculated error magnitudes are then applied to the errored symbols to produce corrected symbols. The syndrome vector, error locations, erasure locations, and error magnitudes may be stored only in the working store, or may be stored to the secondary store, depending on the available resources. The errored symbols and corrected symbols are preferably stored in the secondary store.
In a preferred embodiment, an incoming serial stream of symbols is provided that is protected by a linear block error-correction code. The serial stream of symbols preferably has N symbols, with K symbols being original data symbols (K less than N), and Nxe2x88x92K symbols being redundant symbols. A syndrome vector is first initialized to zero. Next, a decoding matrix is made available, wherein the decoding matrix has N columns and xe2x80x9cNxe2x88x92Kxe2x80x9d rows. The decoding matrix may be calculated algorithmically on-the-fly, as symbols are received.
The serial stream of symbols, ri, are then received, where xe2x80x9cixe2x80x9d is an integer from 1 to N that identifies a particular one of the symbols within the serial stream of symbols. For each received symbol, ri, it is determined if the received symbol corresponds to an erasure location. If so, the index xe2x80x9cixe2x80x9d is recorded as an erasure location, and ri is set to zero.
Thereafter, the received symbol, ri, is multiplied by the entries in the xe2x80x9cithxe2x80x9d column of the decoding matrix, thereby resulting in xe2x80x9cNxe2x88x92Kxe2x80x9d intermediate syndrome components. The xe2x80x9cNxe2x88x92Kxe2x80x9d intermediate syndrome components are added to the corresponding entry in the syndrome vector. If the received symbol, ri, is one of the original data symbols, the symbol, ri, is stored to the secondary store. Once all N of the received symbols ri are received, the error locations are calculated using the syndrome vector and the identified erasure locations. Using the error locations and the syndrome vector, an error vector, e, is calculated. The error vector, e, identifies the error magnitudes for selected symbols in the received stream of symbols.
For each erasure location, j, the additive inverse of the error magnitude ej is calculated, or xe2x88x92ej. The additive inverse xe2x88x92ej is then stored in the secondary store, preferably overwriting the symbol that corresponds to the erasure location, j. For each non-erasure error location, the error magnitude ej is subtracted from the corresponding errored symbol resulting in a corrected symbol. The corrected symbol is then stored in the secondary store, preferably overwriting the errored symbol that corresponds to the non-erasure error location.
The received symbols are preferably stored to the secondary store sequentially as they are received (i.e. in interleaved order). It is sometimes beneficial, therefore, for the symbols to be transmitted in the same order presented to the encoder/interleaver, as this may improve the readout performance of the corrected data from the secondary store (e.g., disk) when sequential access is more efficient than random access. To accomplish this, each symbol of an object may be assigned to one of a number of blocks. An object may be, for example, a digital stream of symbols that collectively represent a new story, a video clip, or any other unit or topic of information. Each of the blocks is encoded using a conventional block error-correction code. The symbols from two or more of the blocks are then interleaved to provide a stream of output symbols. The assigning, encoding and interleaving algorithms are preferably configured so that the stream of output symbols is delivered in the original order of the object. This may be accomplished by assigning the symbols to the blocks in the same order as the interleaver interleaves the symbols of the blocks.